package datastructure.book.dp._2_linear_pre_section.single.all;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class _14_Solution {

    public int longestArithSeqLength(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        Arrays.fill(dp[0],2);
        int max = 2;
        for (int i = 1; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                int tolerance = nums[j] - nums[i];
                int pre = nums[i] - tolerance;
                int preIndex = -1;
                for (int k = i-1; k >= 0; k--) {
                    if (nums[k] == pre) {
                        preIndex = k;
                        break;
                    }
                }
                if (preIndex == -1) {
                    dp[i][j] = 2;
                } else {
                    dp[i][j] = dp[preIndex][i]+1;
                    max = Math.max(max,dp[i][j]);
                }
            }
        }
        return max;
    }

    @Test
    public void test(){
        int[] arr = new int[]{20,1,15,3,10,5,8};
        System.out.println(longestArithSeqLength(arr));
    }
}
